// https://leetcode.cn/problems/n-th-tribonacci-number/
#include <bits/stdc++.h>
using namespace std;

vector<vector<long long>> multiply(const vector<vector<long long>> &a, const vector<vector<long long>> &b) {
    vector<vector<long long>> ret(a.size(), vector<long long>(b[0].size()));
    for (long long i = 0; i < a.size(); i++) {
        for (long long j = 0; j < b[0].size(); j++) {
            for (long long k = 0; k < b.size(); k++) {
                ret[i][j] += a[i][k] * b[k][j];
            }
        }
    }
    return ret;
}

vector<vector<long long>> matrixPower(vector<vector<long long>> &a, long long p) {
    vector<vector<long long>> ret(a.size(), vector<long long>(a.size()));
    for (long long i = 0; i < a.size(); i++) ret[i][i] = 1;
    while (p) {
        if (p & 1) {
            ret = multiply(ret, a);
        }
        p >>= 1;
        a = multiply(a, a);
    }
    return ret;
}

long long solve(long long n) {
    if (n == 0) return 0;
    if (n <= 2) return 1;
    vector<vector<long long>> ret(1, vector<long long>(3, 1)), fac = {
        {1, 1, 0},
        {1, 0, 1},
        {1, 0, 0}
    };
    ret[0][2] = 0;
    ret = multiply(ret, matrixPower(fac, n - 2));
    return ret[0][0];
}

long long tribonacci(long long n) {
    return solve(n);
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;
    return 0;
}